package top.minuy.structure.linear.array;
/**
 * @author Minuy
 * @time 11:46
 * @date 2021/8/21
 */
public class Array<E> {
    // 数据数组
    private E[] data;
    // 数组元素个数
    private int size;

    /**
     * 创建数组，并设置初始容量
     *
     * @param capacity 容量
     */
    public Array(int capacity) {
        this.data = (E[]) new Object[capacity];
    }

    /**
     * 使用默认容量10来创建数组
     */
    public Array() {
        this(10);
    }

    /**
     * 传入一个数组，转换成动态数组
     *
     * @param arr 数组
     */
    public Array(E[] arr) {
        this(arr.length);
        for (int i = 0; i < arr.length; i++) {
            data[i] = arr[i];
        }
        size = arr.length;
    }

    /**
     * 获取数组元素个数
     *
     * @return 元素个数
     */
    public int getSize() {
        return this.size;
    }

    /**
     * 获取数组容量
     *
     * @return 容量
     */
    public int getCapacity() {
        return this.data.length;
    }

    /**
     * 判断是否是空数组
     *
     * @return 是否为空
     */
    public boolean isEmpty() {
        return this.size == 0;
    }

    /**
     * 向数组末尾插入一个元素
     *
     * @param e 需要插入的元素
     */
    public void addLast(E e) {
        this.add(this.size, e);
    }

    /**
     * 向数组最前面插入一个元素
     *
     * @param e 需要插入的元素
     */
    public void addFirst(E e) {
        this.add(0, e);
    }

    /**
     * 向数组任意位置插入元素
     *
     * @param index 要插入的位置
     * @param e     要插入的元素
     */
    public void add(int index, E e) {
        // 判断索引在可插入范围内
        if (index < 0 || index > this.size) {
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index =< size.");
        }

        // 判断容量是否满了
        if (size >= this.getCapacity()) {
            resize(this.getCapacity() * 2);
        }

        int i = this.size;
        while (i > index) {
            this.data[i] = this.data[i - 1];
            i--;
        }

        this.data[index] = e;
        this.size++;
    }

    /**
     * 重新调整数组的大小
     *
     * @param size 数组新的大小
     */
    private void resize(int size) {
        E[] newData = (E[]) new Object[size];

        //if (this.size >= 0) System.arraycopy(this.data, 0, newData, 0, this.size);

        for (int i = 0; i < this.size; i++) {
            newData[i] = this.data[i];
        }

        this.data = newData;
    }

    /**
     * 查找一个元素是否存在数组中
     *
     * @param e 要查找的元素
     * @return 是否存在数组中
     */
    public boolean contains(E e) {
        for (int i = 0; i < this.size; i++) {
            if (this.data[i].equals(e)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 查找一个元素的位置
     *
     * @param e 元素
     * @return 位置，未找到返回-1
     */
    public int find(E e) {
        for (int i = 0; i < this.size; i++) {
            if (this.data[i].equals(e)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 找出这个元素的所有索引
     *
     * @param e 元素
     * @return 所有索引数组
     */
    public int[] findAll(E e) {
        int[] allIndex = new int[this.size];
        int index = 0;
        for (int i = 0; i < this.size; i++) {
            if (this.data[i].equals(e)) {
                allIndex[index] = i;
                index++;
            }
        }

        int[] res = new int[index];

        int i = 0;
        while (i < index) {
            res[i] = allIndex[i];
            i++;
        }

        return res;
    }

    /**
     * 删除一个指定位置的元素
     *
     * @param index 指定位置
     * @return 被删除的元素
     */
    public E remove(int index) {
        if (index < 0 || index >= this.size) {
            throw new IllegalArgumentException("Remove failed. index is illegal.");
        }
        E res = this.data[index];
        for (int i = index; i + 1 < this.size; i++) {
            this.data[i] = this.data[i + 1];
        }

        this.size--;

        // 提前释放内存
        this.data[size] = null;

        // 判断是否要收紧内存
        // 个人认为比例常数跟增加的不一样可以防止临界点时候反复横跳消耗性能
        // 比较小的话是收紧内存
        /*
         * 通过后面的章节得知，这是一种复杂度震荡的现象，处理的话需要懒处理，我的这个
         * 处理方式还不够好
         * */
        //int resize = (int)(this.data.length/1.8);
        //if(this.size<resize){
        //    this.resize(resize);
        //}

        if (this.size < this.data.length / 4 && this.data.length / 2 != 0) {
            this.resize(this.data.length / 2);
        }

        return res;
    }

    /**
     * 快捷方法，删除第一个元素
     *
     * @return 被删除的元素值
     */
    public E removeFirst() {
        return remove(0);
    }

    /**
     * 快捷方法，删除最后一个元素
     *
     * @return 被删除的元素
     */
    public E removeLast() {
        return remove(this.size - 1);
    }

    /**
     * 删除一个元素，如果此元素存在
     *
     * @param e 要删除的元素
     * @return 被删除元素的索引
     */
    public int removeElement(E e) {
        int index = find(e);
        if (index != -1) {
            remove(index);
        }
        return index;
    }

    /**
     * 删除所有的这个元素
     *
     * @param e 元素
     * @return 被删除的索引数组
     */
    public int[] removeAllElement(E e) {
        int[] index = findAll(e);

        // 这里要保证index的排序是从小到大
        for (int i = index.length - 1; i >= 0; i--) {
            remove(index[i]);
        }

        return index;
    }

    /**
     * 获取数组中的元素
     *
     * @param index 元素索引
     * @return 元素
     */
    public E get(int index) {
        if (index < 0 || index >= this.size) {
            throw new IllegalArgumentException("Get failed, index is illegal");
        }

        return this.data[index];
    }

    /**
     * 获取最后一个元素
     *
     * @return 最后一个元素
     */
    public E getLast() {
        return get(size - 1);
    }

    /**
     * 获取最前一个元素
     *
     * @return 最前一个元素
     */
    public E getFirst() {
        return get(0);
    }

    /**
     * 修改数组中的元素
     *
     * @param index 需要修改的索引
     * @param e     修改后的值
     */
    public void set(int index, E e) {
        if (index < 0 || index >= this.size) {
            throw new IllegalArgumentException("Set failed, index is illegal");
        }

        this.data[index] = e;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array : size = %d , capacity = %d\n", this.size, this.getCapacity()));
        res.append("[");
        for (int i = 0; i < this.size; i++) {
            res.append(this.data[i]);
            if (i != this.size - 1) {
                res.append(", ");
            }
        }
        res.append("]");
        return res.toString();
    }

    /**
     * 交换两个元素
     *
     * @param i 元素1索引
     * @param j 元素2索引
     */
    public void swap(int i, int j) {
        if (i == j) {
            return;
        }

        if (i >= 0 && j >= 0 && i < size && j < size) {
            E t = data[i];
            data[i] = data[j];
            data[j] = t;
        } else {
            throw new IllegalArgumentException("Swap failed. Index is illegal.");
        }
    }




    /**
     * 返回大小的重载
     *
     * @return int 数组大小
     * @author Minuy
     * @date 2021/11/15 19:51
     */
    public int size(){
        return getSize();
    }

    /**
     * 默认是添加到结尾
     *
     * @param e 要添加的元素
     * @author Minuy
     * @date 2021/11/15 19:50
     */
    public void add(E e) {
        addLast(e);
    }

}
